An application program stores and manipulates data in files and in directories via a file system. The file system allocates and de-allocates disk blocks in response to application program requests. Data stored in the files and directories are broken down into smaller segments of bytes and mapped to disk blocks. Thus disk blocks are allocated to store data according to service requests made by the application program. A block allocation map is used to keep track of the disk blocks as they are allocated so that the disk blocks may be retrieved by the application program. Thus, the algorithm used by a file system to allocate disk blocks affects how efficiently the file system stores and retrieves data and therefore, how efficiently the file system is able to service requests made by the application program.
File systems based on a sequential access storage layer, such as IBM's Journaled File System (JFS), realize significant performance benefits when accessing disk blocks that are physically, or logically, contiguous on a disk, despite the overhead required to maintain contiguous disk blocks. For example, because a sequential access file system must access disk blocks in a predetermined order, the file system could service a request for a group of disk blocks more efficiently if those disk blocks were physically, or logically, located next to each other in the file system. If the same group of disk blocks were dispersed throughout the disk in a noncontiguous manner, the file system would require more time to access the disk blocks since the storage media would need to do multiple seeks over the disk, at the storage layer, to read all of the disk blocks in the group.
File systems utilizing random disk access, however, do not realize much in performance gains by maintaining physically or logically contiguous disk blocks. To the contrary, maintaining contiguous disk blocks by the file system hinders performance if the underlying storage media is a random access device. Specifically, random access devices can access disk blocks consistently, regardless of the physical or logical location of disk blocks and regardless of the order in which disk blocks are accessed. In other words, the amount of time in which a random access device can access disk blocks does not change significantly if the disk blocks are not contiguous. Maintaining contiguous disk blocks, therefore, results in unnecessary overhead for the file system when allocating and de-allocating disk blocks for its files.